package com.haohuo.question4;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author mike
 */
public class Order {

    /**
     * 测试入口
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] orderArray = new int[]{1, 2, 3, 6, 4, 11, 12, 13, 16, 14, 21, 22, 23, 26, 34};
        int target = 98;
        Order order = new Order();
        List<List<Integer>> lists = order.calcOrder(orderArray, target);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }

    /**
     * 计算订单可以支付的方案
     *
     * @param orderArray 订单金额（int分）
     * @param target     目标总金额（int分）
     */
    public List<List<Integer>> calcOrder(int[] orderArray, int target) {
        List<List<Integer>> resultList = new LinkedList<>();
        int temp = 0;
        //获取所有子集
        List<List<Integer>> subsets = subsets(orderArray);
        for (List<Integer> subset : subsets) {
            int sum = 0;
            for (Integer i : subset) {
                sum = sum + i;
            }
            //比较金额大小并保存
            if (sum <= target) {
                if (sum == temp) {
                    temp = sum;
                    resultList.add(subset);
                } else if (sum > temp) {
                    temp = sum;
                    resultList.clear();
                    resultList.add(subset);
                }
            }
        }
        return resultList;

    }

    /**
     * 获取所有子集
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<Integer> t = new ArrayList<Integer>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }
}
